//30.04.2007
// no memory losing
// good formating
//?? static+public: variables & function
//?? dll
//?? array

#include "stdafx.h"
#include <math.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>

int		gridSize	=	40;
//coefficients for evaluation function
double	k1	=	2.0;
double	k2	=	-2.0;
double	k3	=	-2.5;
double	k4	=	0.25;
double	k5	=	-1.0;
double	k6	=	0;
//elite
int	elite	=	4;
//convergence
int k		=	500;
int maxIter	=	10000;
//options
void setConvergence(int x)
{
	k	=	x;
}
void setMaxIterations(int x)
{
	maxIter	=	x;
}
void setElite(int x)
{
	elite	=	x;
}
//set coefficients for evaluation function
void setCoefficient(double mk1,double mk2,double mk3,double mk4,double mk5)
{
	k1	=	fabs(mk1);
	k2	=	-fabs(mk2);
	k3	=	-fabs(mk3);
	k4	=	fabs(mk4);
	k5	=	-fabs(mk5);
}
//orient draw
void orientDraw(double mk6)
{
		k6	=	-fabs(mk6);
}
void nonOrientDraw()
{
		k6	=	0;
}
//Geometria, geographia
double lengthBetween(int x1,int y1,int x2,int y2)
{
	return sqrt(pow(x1-x2,2.0)+pow(y1-y2,2.0));
}

double dx(int x0,int y0,int x1,int y1,int x,int y)
{
	double	ret		=	0;
	double	l		=	lengthBetween(x0,y0,x1,y1),
			l1		=	lengthBetween(x1,y1,x,y),
			l0		=	lengthBetween(x0,y0,x,y);
	double	cos0	=	(l*l+l0*l0-l1*l1)/(2*l0*l);
	double	cos1	=	(l*l+l1*l1-l0*l0)/(2*l1*l);
	double	sin0	=	sqrt(1-cos0*cos0);

	if((cos0<0)||(cos1<0))
	{
		ret	=	(l0>l1?l1:l0);
	}
	else
	{
		ret	=	l0*sin0;
	}

	return ret;
}
int isContain(int xSquare,int ySquare,int squareSize,int x,int y)
{
	bool ret	=	0;
	bool inx,iny;

	inx	=	((x-xSquare)*(x-(xSquare+squareSize))<=0);
	iny	=	((y-ySquare)*(y-(ySquare+squareSize))<=0);
	ret	=	(inx)&&(iny);

	return ret;
}

int isIntersectionSquare(int xSquare1,int ySquare1,int xSquare2,int ySquare2,int squareSize)
{
	int ret	=	0;

	if(isContain(xSquare1,ySquare1,squareSize,xSquare2,ySquare2)&&(isContain(xSquare1,ySquare1,squareSize,xSquare2,ySquare2+squareSize))&&(isContain(xSquare1,ySquare1,squareSize,xSquare2+squareSize,ySquare2+squareSize))&&(isContain(xSquare1,ySquare1,squareSize,xSquare2+squareSize,ySquare2)))
		ret	=	1;

	return ret;
}
bool isIntersect2(int x11,int y11,int x12,int y12,int x21,int y21,int x22,int y22)
{
	double	t1,t2;
	bool	ret	=	false;
	bool	inv11,inv12,inv21,inv22;
	int		dx1,dx2,dx,dy1,dy2,dy,dx3,dy3;
	
	dx1	=	x12-x11;
	dx2	=	x22-x21;

	dy1	=	y12-y11;
	dy2	=	y22-y21;
	
	dx	=	x21-x11;
	dy	=	y21-y11;

	dx3	=	x22-x11;
	dy3	=	y22-x11;

	if(dx1*dy2!=dx2*dy1)
	{
		t2	=	-(double(dy*dx1-dx*dy1)/(dx1*dy2-dx2*dy1));
		t1	=	-(double(dy*dx2-dx*dy2)/(dx1*dy2-dx2*dy1));
		if((t1>=0.0)&&(t1<=1.0)&&(t2>=0.0)&&(t2<=1.0))
		{
			ret	=	true;
		}
	}
	else
	{
		//Parallel segments
		inv11	=	((x11-x21)*(x11-x22)<0)&&((y11-y21)*(y11-y22)<=0);
		inv12	=	((x12-x21)*(x12-x22)<0)&&((y12-y21)*(y12-y22)<=0);
		inv21	=	((x21-x11)*(x21-x12)<0)&&((y21-y11)*(y21-y12)<=0);
		inv22	=	((x22-x11)*(x22-x12)<0)&&((y22-y11)*(y22-y12)<=0);
		
		if(inv11||inv12||inv21||inv22)
		{
			ret	=	true;
		}
	}

	return ret;
}

int calculateGridSize(int x)
{
	int ret	=	(sqrt((double)x*10)+1);

	if(ret>40)
		ret	=	40;

	return ret;
}
double optLenCalculate(int n)
{
	double ret	=	0;

	for(int i=1;i<=n;i++)
	{
		ret	=	ret+sqrt(gridSize*gridSize*(1-fabs(cos(2*3.14/i)))/2);
	}
	ret	=	ret/n;

	return ret;
}
int randomCustom(int x)
{
	int ret	=	0;

	if(x)
		ret	=	rand()%x+1;

	return ret;
}
void calculateDeg(int *MI,int *Deg,int m,int n)
{
	int i;

	for(i=0;i<n;i++)
	{
		Deg[i]=0;
	}
	for(i=1;i<=m;i++)
	{
		Deg[(MI[(i-1)*2]-1)]	=	Deg[(MI[(i-1)*2]-1)]+1;
		Deg[(MI[(i-1)*2+1]-1)]	=	Deg[(MI[(i-1)*2+1]-1)]+1;
	}
}

int findVertDeg(int *Deg,int needDeg,int n)
{
	int i;
	int ret			=	-1;
	int count		=	0;
	int *needDegV	=	new int[n];
	
	for(i=1;i<=n;i++)
		if(Deg[i-1]>=needDeg)
		{
			needDegV[count]	=	i;
			count++;
		}
	if(count)
	{
		ret	=	needDegV[randomCustom(count)-1];
	}

	delete[n] needDegV;

	return ret;
}

void copyArray(int *from,int *to,int size)
{
	int i;

	for(i=0;i<size;i++)
	{
		to[i]	=	from[i];
	}
}
void sort2(int *order,double *popEF,int n)
{
	int i,j,hold;

	for(i=1;i<n;i++)
	{
		for(j=0;j<n-1;j++)
		{
			if(popEF[order[j]]<popEF[order[j+1]])
			{
				hold		=	order[j];
				order[j]	=	order[j+1];
				order[j+1]	=	hold;
			}
		}
	}
}
int isConvergence(double *EF,double eps,int x)
{
	int ret	=	1;
	int i	=	0;
	
	while((i<x-1)&&(ret))
	{
		if(fabs(EF[i]-EF[i+1])>=eps)
		{
			ret	=	0;
		}
		i++;
	}

	return ret;
}
//Mutation (8 pieces+totalMutate)
void SingleMutate(int *Emb,int n)
{
	int		x	=	randomCustom(n);
	int		xnew,ynew,i;
	bool	find;
	
	do
	{
		xnew	=	randomCustom(gridSize);
		ynew	=	randomCustom(gridSize);
		find	=	false;
		i		=	1;
		while((i<=n)&&(!find))
		{
			if((xnew==Emb[(i-1)*2])&&(ynew==Emb[(i-1)*2+1]))
					find	=	true;
			i++;
		}
	}
	while(find);

	Emb[(x-1)*2]	=	xnew;
	Emb[(x-1)*2+1]	=	ynew;
}
void SmallMutate(int *Emb,int n)
{
	int v1	=	randomCustom(n);
	int v2	=	randomCustom(n);
	int x1	=	Emb[(v2-1)*2];
	int y1	=	Emb[(v2-1)*2+1];

	while(v1==v2)
	{
		v1	=	randomCustom(n);
	}

	Emb[(v2-1)*2]	=	Emb[(v1-1)*2];
	Emb[(v2-1)*2+1]	=	Emb[(v1-1)*2+1];
	Emb[(v1-1)*2]	=	x1;
	Emb[(v1-1)*2+1]	=	y1;
}
void TinyMutate(int *Emb,int n,int *Movements)
{
	int v	=	randomCustom(n); 
	int x	=	Emb[(v-1)*2];
	int y	=	Emb[(v-1)*2+1];
	int x1,y1;
	int i,j,k;
	int find;
		i		=	0;
		find	=	1;
		k		=	randomCustom(8)-1;
	while((i<8)&&(find))
	{
		x1	=	x+Movements[k*2];
		y1	=	y+Movements[k*2+1];
		k	=	(k+1)%8;

		if((x1<=gridSize)&&(x1>=1)&&(y1<=gridSize)&&(y1>=1))
		{
			find	=	0;
			j		=	1;
			while((!find)&&(j<=n))
			{
				if((x1==Emb[(j-1)*2])&&(y1==Emb[(j-1)*2+1]))
					find	=	1;
				j++;
			}
		}
		else
		{
			find	=	1;
		}
		i++;
	}

	if(!find)
	{
		Emb[(v-1)*2]	=	x1;
		Emb[(v-1)*2+1]	=	y1;
	}
	
}
void EdgeMutation1(int *Emb,int *MI,int n,int m)
{
	int j,find,x,y,x1,y1;

	int e	=	randomCustom(m);
	int v1	=	MI[(e-1)*2];
	int v2	=	MI[(e-1)*2+1];

	do
	{   
		x	=	randomCustom(gridSize);
		y	=	randomCustom(gridSize);
		x1	=	randomCustom(gridSize);
		y1	=	randomCustom(gridSize);

		if((x!=x1)||(y!=y1))
		{
			j		=	1;
			find	=	0;
			while((j<=n)&&(!find))
			{
				if(((Emb[(j-1)*2]==x)&&(Emb[(j-1)*2+1]==y))||((Emb[(j-1)*2]==x1)&&(Emb[(j-1)*2+1]==y1)))
					find	=	1;
				j++;
			}
		}
		else
		{
			find	=	1;
		}
	}
	while(find);
	Emb[(v1-1)*2]	=	x;
	Emb[(v1-1)*2+1]	=	y;
	Emb[(v2-1)*2]	=	x1;
	Emb[(v2-1)*2+1]	=	y1;
}
void EdgeMutation2(int *Emb,int *MI,int n,int m)
{
	int j,find,x,y,dx,dy,
		iteration	=	0;
	int e			=	randomCustom(m);
	int v1			=	MI[(e-1)*2];
	int v2			=	MI[(e-1)*2+1];
		dx			=	Emb[(v2-1)*2]-Emb[(v1-1)*2];
		dy			=	Emb[(v2-1)*2+1]-Emb[(v1-1)*2+1];
	do
	{
		//Generate new position		
		if(dx>0)
		{
			x	=	randomCustom(gridSize-dx);
		}
		else
		{
			x	=	randomCustom(gridSize+dx)-dx;
		}

		if(dy>0)
		{
			y	=	randomCustom(gridSize-dy);
		}
		else
		{
			y	=	randomCustom(gridSize+dy)-dy;
		}

		j		=	1;
		find	=	0;

		while((j<=n)&&(!find))
		{
			if(((Emb[(j-1)*2]==x)&&(Emb[(j-1)*2+1]==y))||((Emb[(j-1)*2]==x+dx)&&(Emb[(j-1)*2+1]==y+dy)))
				find	=	1;
			j++;
		}
		iteration++;

	}
	while((find)&&(iteration<50));

	if(!find)
	{
		Emb[(v1-1)*2]	=	x;
		Emb[(v1-1)*2+1]	=	y;
		Emb[(v2-1)*2]	=	x+dx;
		Emb[(v2-1)*2+1]	=	y+dy;
	}
}
void TinyEdgeMove(int *Emb,int *MI,int n,int m,int *Movements)
{
	int i,j,k,find,x,y,dx,dy;

	int e	=	randomCustom(m);
	int v1	=	MI[(e-1)*2];
	int v2	=	MI[(e-1)*2+1];
		dx		=	Emb[(v2-1)*2]-Emb[(v1-1)*2];
		dy		=	Emb[(v2-1)*2+1]-Emb[(v1-1)*2+1];
		i		=	0;
		find	=	1;
		k		=	randomCustom(8)-1;

	while((i<8)&&(find))
	{
		//Generate new position
		x	=	Emb[(v1-1)*2]+Movements[k*2];
		y	=	Emb[(v1-1)*2+1]+Movements[k*2+1];
		k	=	(k+1)%8;

		if((x>=1)&&(x<=gridSize)&&(y>=1)&&(y<=gridSize)&&(x+dx>=1)&&(x+dx<=gridSize)&&(y+dy>=1)&&(y+dy<=gridSize))
		{
			j		=	1;
			find	=	0;
			while((j<=n)&&(!find))
			{
				if(((Emb[(j-1)*2]==x)&&(Emb[(j-1)*2+1]==y))||((Emb[(j-1)*2]==x+dx)&&(Emb[(j-1)*2+1]==y+dy)))
					find	=	1;
				j++;
			}
		}
		else
		{
			find	=	1;
		}
		i++;
	}
	if(!find)
	{
		Emb[(v1-1)*2]	=	x;
		Emb[(v1-1)*2+1]	=	y;
		Emb[(v2-1)*2]	=	x+dx;
		Emb[(v2-1)*2+1]	=	y+dy;
	}
}


void TwoEdgeMutation(int *MI,int *Emb,int n,int m,int *Movements,int *Deg)
{
	int v1	=	findVertDeg(Deg,2,n);
	int v2,v3,newv;
	int i,dx2,dx3,dy2,dy3,x,y,find,k,j;
	if(v1!=-1)
	{
		i	=	1;
		v2	=	0;
		v3	=	0;

		while((i<=m)&&((v2==0)||(v3==0)))
		{
			newv	=	0;
			if(MI[(i-1)*2]==v1)
			{
				newv	=	MI[(i-1)*2+1];

			}
			else
			{
				if(MI[(i-1)*2+1]==v1)
				{
					newv	=	MI[(i-1)*2];
				}
			}
			if(newv)
			{
				if(v2)
				{
					v3	=	newv;
				}
				else
				{
					v2	=	newv;
				}
			}
			i++;
		}

		dx2	=	Emb[(v2-1)*2]-Emb[(v1-1)*2];
		dx3	=	Emb[(v3-1)*2]-Emb[(v1-1)*2];

		dy2	=	Emb[(v2-1)*2+1]-Emb[(v1-1)*2+1];
		dy3	=	Emb[(v3-1)*2+1]-Emb[(v1-1)*2+1];
		
		i		=	0;
		find	=	1;
		k		=	randomCustom(8)-1;
		while((i<8)&&(find))
		{
		//Generate new position
			x	=	Emb[(v1-1)*2]+Movements[k*2];
			y	=	Emb[(v1-1)*2+1]+Movements[k*2+1];
			k	=	(k+1)%8;

			if((x>=1)&&(x<=gridSize)&&(y>=1)&&(y<=gridSize)&&(x+dx2>=1)&&(x+dx2<=gridSize)&&(y+dy2>=1)&&(y+dy2<=gridSize)&&(x+dx3>=1)&&(x+dx3<=gridSize)&&(y+dy3>=1)&&(y+dy3<=gridSize))
			{
				j		=	1;
				find	=	0;
				while((j<=n)&&(!find))
				{
					if(((Emb[(j-1)*2]==x)&&(Emb[(j-1)*2+1]==y))||((Emb[(j-1)*2]==x+dx2)&&(Emb[(j-1)*2+1]==y+dy2))||((Emb[(j-1)*2]==x+dx3)&&(Emb[(j-1)*2+1]==y+dy3)))
						find	=	1;
					j++;
				}
			}
			else
			{
				find	=	1;
			}
			i++;
		}
		if(!find)
		{
			Emb[(v1-1)*2]	=	x;
			Emb[(v1-1)*2+1]	=	y;
			Emb[(v2-1)*2]	=	x+dx2;
			Emb[(v2-1)*2+1]	=	y+dy2;
			Emb[(v3-1)*2]	=	x+dx3;
			Emb[(v3-1)*2+1]	=	y+dy3;
		}
	}
}

void LargeContMutate(int *MI,int *Emb,int n,int m)
{
	//Choose square
	int squareSize	=	2;
	int xSquare1	=	randomCustom(gridSize-squareSize);
	int ySquare1	=	randomCustom(gridSize-squareSize);

	int xSquare2;
	int ySquare2;

	do
	{
		xSquare2	=	randomCustom(gridSize-squareSize);
		ySquare2	=	randomCustom(gridSize-squareSize);
	}
	while(isIntersectionSquare(xSquare1,ySquare1,xSquare2,ySquare2,squareSize));
	
	//Calculating inner vert
	int *Square1	=	new int [(squareSize+1)*(squareSize+1)];
	int count1		=	0;
	int *Square2	=	new int [(squareSize+1)*(squareSize+1)];
	int count2		=	0;
	int i,x,y;

	for(i=1;i<=n;i++)
	{
		x	=	Emb[(i-1)*2];
		y	=	Emb[(i-1)*2+1];

		if(isContain(xSquare1,ySquare1,squareSize,x,y))
		{
			Square1[count1]	=	i;
			count1++;
		}

		if(isContain(xSquare2,ySquare2,squareSize,x,y))
		{
			Square2[count2]	=	i;
			count2++;
		}
	}
	//Exchange
	int v;

	for(i=0;i<count1;i++)
	{
		v				=	Square1[i];
		Emb[(v-1)*2]	=	xSquare2-(xSquare1-Emb[(v-1)*2]);
		Emb[(v-1)*2+1]	=	ySquare2-(ySquare1-Emb[(v-1)*2+1]);
	}

	for(i=0;i<count2;i++)
	{
		v=Square2[i];
		Emb[(v-1)*2]	=	xSquare1-(xSquare2-Emb[(v-1)*2]);
		Emb[(v-1)*2+1]	=	ySquare1-(ySquare2-Emb[(v-1)*2+1]);
	}

	delete[(squareSize+1)*(squareSize+1)] Square1;
	delete[(squareSize+1)*(squareSize+1)] Square2;
}

void Mutate(int *MI,int *Emb,int n,int m,int *PMutate,int *Movements,int *Deg)
{
	int selectMutate,
		i,
		total		=	0;

	for(i=0;i<8;i++)
		total	=	total	+	PMutate[i];

	selectMutate	=	randomCustom(total);
	i				=	0;
	total			=	0;

	while((i<8)&&(selectMutate>total))
	{
		total	=	total+PMutate[i];
		i++;
	}

	selectMutate	=	i;
	switch (selectMutate)
	{
	case 1:
		SingleMutate(Emb,n);
		break;
	case 2:
		SmallMutate(Emb,n);
		break;
	case 3:
		TinyMutate(Emb,n,Movements);
		break;
	case 4:
		EdgeMutation1(Emb,MI,n,m);
		break;
	case 5:
		EdgeMutation2(Emb,MI,n,m);
		break;
	case 6:
		TwoEdgeMutation(MI,Emb,n,m,Movements,Deg);
	case 7:
		TinyEdgeMove(Emb,MI,n,m,Movements);
		break;
	case 8:
		LargeContMutate(MI,Emb,n,m);
		break;
	default:
		break;
	}

}
//crossover
void rectCrossover(int *parent1,int *parent2,int *child1,int *child2,int n)
{
	int sqSize	=	2;
	int p1SqX	=	randomCustom(gridSize-sqSize),
		p1SqY	=	randomCustom(gridSize-sqSize),
		
		p2SqX	=	randomCustom(gridSize-sqSize),
		p2SqY	=	randomCustom(gridSize-sqSize),
		
		c1SqX	=	randomCustom(gridSize-sqSize),
		c1SqY	=	randomCustom(gridSize-sqSize),
		
		c2SqX	=	randomCustom(gridSize-sqSize),
		c2SqY	=	randomCustom(gridSize-sqSize);

	int *p1Sq	=	new int[(sqSize+1)*(sqSize+1)];
	int *p2Sq	=	new int[(sqSize+1)*(sqSize+1)];
	int i,
		count1	=	0,
		count2	=	0;

	//Whats in sqaure
	for(i=1;i<=n;i++)
	{
		//in p1Sq
		if(isContain(p1SqX,p1SqY,sqSize,parent1[(i-1)*2],parent1[(i-1)*2+1]))
		{
			child2[(i-1)*2]		=	0;
			child2[(i-1)*2+1]	=	0;
			p1Sq[count1]		=	i;
			count1++;
		}
		else
		{
			child2[(i-1)*2]		=	parent2[(i-1)*2];
			child2[(i-1)*2+1]	=	parent2[(i-1)*2+1];
		}
		//in p2Sq
		if(isContain(p2SqX,p2SqY,sqSize,parent2[(i-1)*2],parent2[(i-1)*2+1]))
		{
			child1[(i-1)*2]		=	0;
			child1[(i-1)*2+1]	=	0;
			p2Sq[count2]		=	i;
			count2++;
		}
		else
		{
			child1[(i-1)*2]		=	parent1[(i-1)*2];
			child1[(i-1)*2+1]	=	parent1[(i-1)*2+1];
		}
	}
	int *c1Sq	=	new int[(sqSize+1)*(sqSize+1)];
	int *c2Sq	=	new int[(sqSize+1)*(sqSize+1)];
	int countC1	=	0,
		countC2	=	0;

	//Exchange
	int		vMove,j,x,y,find;

	//p1->c2
	if(count1>0)
	{
		for(i=0;i<count1;i++)
		{
			vMove					=	p1Sq[i];
			child2[(vMove-1)*2]		=	c2SqX-(p1SqX-parent1[(vMove-1)*2]);
			child2[(vMove-1)*2+1]	=	c2SqY-(p1SqY-parent1[(vMove-1)*2+1]);
			//if move on node
			for(j=1;j<=n;j++)
			{
				if(j!=vMove)
				{
					if((child2[(j-1)*2]==child2[(vMove-1)*2])&&(child2[(j-1)*2+1]==child2[(vMove-1)*2+1]))
					{
						c2Sq[countC1]		=	j;
						child2[(j-1)*2]		=	0;
						child2[(j-1)*2+1]	=	0;
						countC1++;
					}
				}
			}
		}
		for(i=0;i<countC1;i++)
		{
			vMove	=	c2Sq[i];
			do
			{
				x		=	randomCustom(gridSize);
				y		=	randomCustom(gridSize);
				find	=	0;
				j		=	1;
				while((j<=n)&&(!find))
				{
					if((x==child2[(j-1)*2])&&(y==child2[(j-1)*2+1]))
						find	=	1;
					j++;
				}
			}
			while(find);
			child2[(vMove-1)*2]		=	x;
			child2[(vMove-1)*2+1]	=	y;
		}
	}

	//Exchange
	//p2->c1
	if(count2>0)
	{
		for(i=0;i<count2;i++)
		{
			vMove					=	p2Sq[i];
			child1[(vMove-1)*2]		=	c1SqX-(p2SqX-parent2[(vMove-1)*2]);
			child1[(vMove-1)*2+1]	=	c1SqY-(p2SqY-parent2[(vMove-1)*2+1]);
			//if move on node
			for(j=1;j<=n;j++)
			{
				if(j!=vMove)
				{
					if((child1[(j-1)*2]==child1[(vMove-1)*2])&&(child1[(j-1)*2+1]==child1[(vMove-1)*2+1]))
					{
						c1Sq[countC2]		=	j;
						child1[(j-1)*2]		=	0;
						child1[(j-1)*2+1]	=	0;
						countC2++;
					}
				}
			}
		}

		for(i=0;i<countC2;i++)
		{
			vMove	=	c1Sq[i];
			do
			{
				x		=	randomCustom(gridSize);
				y		=	randomCustom(gridSize);
				find	=	0;
				j		=	1;
				while((j<=n)&&(!find))
				{
					if((x==child1[(j-1)*2])&&(y==child1[(j-1)*2+1]))
						find	=	1;
					j++;
				}
			}
			while(find);
			child1[(vMove-1)*2]		=	x;
			child1[(vMove-1)*2+1]	=	y;
		}
	}

	delete[(sqSize+1)*(sqSize+1)] p1Sq;
	delete[(sqSize+1)*(sqSize+1)] p2Sq;
	delete[(sqSize+1)*(sqSize+1)] c1Sq;
	delete[(sqSize+1)*(sqSize+1)] c2Sq;
}
void threeNodeCrossover(int *parent1,int *parent2,int *child1,int *child2,int n,int *MI,int m,int *Deg)
{
	int		v1	=	findVertDeg(Deg,2,n);
	int		v2,v3,newv,i,find;

	if(v1!=-1)
	{
		//Subgraph of three vertices
		i	=	1;
		v2	=	0;
		v3	=	0;

		while((i<=m)&&((v2==0)||(v3==0)))
		{
			newv=0;
			if(MI[(i-1)*2]==v1)
			{
				newv=MI[(i-1)*2+1];

			}
			else
			{
				if(MI[(i-1)*2+1]==v1)
				{
					newv=MI[(i-1)*2];
				}
			}
			if(newv)
			{
				if(v2)
				{
					v3=newv;
				}
				else
				{
					v2=newv;
				}
			}
			i++;
		}

		//Coordinating
		int p1v1x	=	parent1[(v1-1)*2],
			p1v1y	=	parent1[(v1-1)*2+1],
			p1v2x	=	parent1[(v2-1)*2],
			p1v2y	=	parent1[(v2-1)*2+1],
			p1v3x	=	parent1[(v3-1)*2],
			p1v3y	=	parent1[(v3-1)*2+1];
		
		int p2v1x	=	parent2[(v1-1)*2],
			p2v1y	=	parent2[(v1-1)*2+1],
			p2v2x	=	parent2[(v2-1)*2],
			p2v2y	=	parent2[(v2-1)*2+1],
			p2v3x	=	parent2[(v3-1)*2],
			p2v3y	=	parent2[(v3-1)*2+1];

		for(i=1;i<=n;i++)
		{
			if((i!=v1)&&(i!=v2)&&(i!=v1))
			{
				child1[(i-1)*2]		=	parent1[(i-1)*2];
				child1[(i-1)*2+1]	=	parent1[(i-1)*2+1];
				child2[(i-1)*2]		=	parent2[(i-1)*2];
				child2[(i-1)*2+1]	=	parent2[(i-1)*2+1];
			}
			else
			{
				child1[(i-1)*2]	=	child1[(i-1)*2+1]	=	child2[(i-1)*2]		=	child2[(i-1)*2+1]	=	0;
			}
		}

		//Exchange
		//p1->c2
		i=1;
		find=0;
		while((i<=n)&&(!find))
		{
			if(((p1v1x==child2[(i-1)*2])&&(p1v1y==child2[(i-1)*2+1]))||((p1v2x==child2[(i-1)*2])&&(p1v2y==child2[(i-1)*2+1]))||((p1v3x==child2[(i-1)*2])&&(p1v3y==child2[(i-1)*2+1])))
			{
				find	=	1;
			}
			i++;
		}

		if(!find)
		{
			child2[(v1-1)*2]	=	p1v1x;
			child2[(v1-1)*2+1]	=	p1v1y;
			child2[(v2-1)*2]	=	p1v2x;
			child2[(v2-1)*2+1]	=	p1v2y;
			child2[(v3-1)*2]	=	p1v3x;
			child2[(v3-1)*2+1]	=	p1v3y;
		}
		else
		{
			child2[(v1-1)*2]	=	p2v1x;
			child2[(v1-1)*2+1]	=	p2v1y;
			child2[(v2-1)*2]	=	p2v2x;
			child2[(v2-1)*2+1]	=	p2v2y;
			child2[(v3-1)*2]	=	p2v3x;
			child2[(v3-1)*2+1]	=	p2v3y;
		}

		//Exchange
		//p2->c1
		i=1;
		find=0;
		while((i<=n)&&(!find))
		{
			if(((p2v1x==child1[(i-1)*2])&&(p2v1y==child1[(i-1)*2+1]))||((p2v2x==child1[(i-1)*2])&&(p2v2y==child1[(i-1)*2+1]))||((p2v3x==child1[(i-1)*2])&&(p2v3y==child1[(i-1)*2+1])))
			{
				find	=	1;
			}
			i++;
		}

		if(!find)
		{
			child1[(v1-1)*2]	=	p2v1x;
			child1[(v1-1)*2+1]	=	p2v1y;
			child1[(v2-1)*2]	=	p2v2x;
			child1[(v2-1)*2+1]	=	p2v2y;
			child1[(v3-1)*2]	=	p2v3x;
			child1[(v3-1)*2+1]	=	p2v3y;
		}
		else
		{
			child1[(v1-1)*2]	=	p1v1x;
			child1[(v1-1)*2+1]	=	p1v1y;
			child1[(v2-1)*2]	=	p1v2x;
			child1[(v2-1)*2+1]	=	p1v2y;
			child1[(v3-1)*2]	=	p1v3x;
			child1[(v3-1)*2+1]	=	p1v3y;
		}
	}
}
void Crossover(int *parent1,int *parent2,int *child1,int *child2,int n,int *MI,int m,int *Deg)
{
	int selectCross	=	randomCustom(3);

	switch(selectCross)
	{
	case 1:
		rectCrossover(parent1,parent2,child1,child2,n);
		break;
	case 2:
		threeNodeCrossover(parent1,parent2,child1,child2,n,MI,m,Deg);
		break;
	case 3:
		copyArray(parent1,child1,2*n);
		copyArray(parent2,child2,2*n);
	default:
		break;
	}
}
//Evolution
double evalutionFunction(int n,int *Emb,int m,int *MI,double optLen)
{
	int		i,j;
	double	ret		=	0;

	//Minimum node distance sum
	double	MNDS	=	0;
	double	min,f;

	for(i=1;i<=n;i++)
	{
		min	=	lengthBetween(1,1,gridSize,gridSize);
		for(j=1;j<=n;j++)
		{
			if(i!=j)
			{
				f	=	lengthBetween(Emb[(i-1)*2],Emb[(i-1)*2+1],Emb[(j-1)*2],Emb[(j-1)*2+1]);
				if(f<min)
					min	=	f;
			}
		}
		MNDS	=	MNDS+min;
	}

	//minimum node distance
	double	MND	=pow(MNDS,2.0)*n;

	//Edle length deviation+orientation
	int		v1,v2,v3,v4;
	double	ELD=0,WO=0,l=0;

	for(i=1;i<=m;i++)
	{
		v1	=	MI[(i-1)*2];
		v2	=	MI[(i-1)*2+1];
		l	=	lengthBetween(Emb[(v1-1)*2],Emb[(v1-1)*2+1],Emb[(v2-1)*2],Emb[(v2-1)*2+1]);
		if(Emb[(v1-1)*2+1]>=Emb[(v2-1)*2+1])
		{
			WO	=	WO+l;
		}
		ELD	=	ELD+fabs(l-optLen);		
	}

	//Edge crossing
	double	EC	=	0;

	for(i=1;i<=m;i++)
	{
		v1	=	MI[(i-1)*2];
		v2	=	MI[(i-1)*2+1];
		for(j=(i+1);j<=m;j++)
		{
			v3	=	MI[(j-1)*2];
			v4	=	MI[(j-1)*2+1];
			
			if(!((v1==v3)||(v2==v3)||(v1==v4)||(v2==v4)))
			{
				if(isIntersect2(Emb[(v1-1)*2],Emb[(v1-1)*2+1],Emb[(v2-1)*2],Emb[(v2-1)*2+1],Emb[(v3-1)*2],Emb[(v3-1)*2+1],Emb[(v4-1)*2],Emb[(v4-1)*2+1]))
				{
					EC	=	EC+1;
				}
			}
		}
	}

	//Edges with Nodes crossing
	double	ENC	=	0;
	double	r	=	1.0/3;

	for(i=1;i<=n;i++)
	{
		for(j=i;j<=m;j++)
		{
			if((MI[(j-1)*2]!=i)&&(MI[(j-1)*2+1]!=i))
			{
				l	=	dx(Emb[(MI[(j-1)*2]-1)*2],Emb[(MI[(j-1)*2]-1)*2+1],Emb[(MI[(j-1)*2+1]-1)*2],Emb[(MI[(j-1)*2+1]-1)*2+1],Emb[(i-1)*2],Emb[(i-1)*2+1]);
				if(l<r)
					ENC	=	ENC+1;
			}
		}
	}

	ret	=	k1*MNDS	+	k2*ELD	+	k3*ELD/MND	+	k4*MND	+k5*(EC+ENC)*gridSize*gridSize	+	k6*WO;
	return ret;
}
void generateEmb(int *Emb,int n)
{
	int i,find,x,y,j;

	for(i=1;i<=n;i++)
	{
		do
		{
			find	=	0;
			x		=	randomCustom(gridSize);
			y		=	randomCustom(gridSize);
			for(j=1;j<i;j++)
			{
				if((Emb[(j-1)*2]==x)&&(Emb[(j-1)*2+1]==y))
				{
					find	=	1;
				}
			}
		}
		while(find);
		Emb[(i-1)*2]	=	x;
		Emb[(i-1)*2+1]	=	y;
	}
}
void generatePopulation(int *Population,int n,int populationSize)
{
	int i;

	for(i=0;i<populationSize;i++)
	{
		generateEmb(Population+i*n*2,n);
	}
}
void calculateEFforPop(int *Population,double *popEF,int n,int *MI,int m,double optLen,int populationSize)
{
	int		i;
	double	EF;

	for(i=0;i<populationSize;i++)
	{
		EF			=	evalutionFunction(n,Population+i*n*2,m,MI,optLen);
		popEF[i]	=	EF;
	}
}

void chooseParents1(int *population,int *parents,int n,int *order,int populationSize)
{
	int		i,j,selectParent,total;
	int		genStep=1;

	for(j=0;j<populationSize;j++)
	{
		total	=	(genStep*(populationSize-1)*(populationSize-2))/2+populationSize;
		selectParent=randomCustom(total);
		total	=	0;
		i		=	0;
		while(total<=selectParent)
		{
			total	=	total+(genStep*i);
			i++;
		}
		selectParent	=	i-1;
		selectParent	=	order[populationSize-selectParent];
		parents[j]		=	selectParent;
	}
}
void generateChilds1(int *parents,int *childs,int n,int *MI,int m,int *Movements,int *PMutate,int *Deg,int populationSize,int *population)
{
	int i;

	for(i=0;i<populationSize/2;i++)
	{
		Crossover(population+parents[i*2]*2*n,population+parents[i*2+1]*2*n,childs+i*2*2*n,childs+(i*2+1)*2*n,n,MI,m,Deg);
		Mutate(MI,childs+i*2*2*n,n,m,PMutate,Movements,Deg);
		Mutate(MI,childs+(i*2+1)*2*n,n,m,PMutate,Movements,Deg);
	}
}
void generateNextGen2(int *population,int *popOrder,int *childs,int *chOrder,int n,int populationSize,double *popEF,double *chEF,int *newGenOrder)
{	
	int		i=0,
			j=0,
			k=0;	
	int		*swap=NULL;
	
	while((j<elite)&&(k<populationSize-elite))
	{
		if(popEF[popOrder[j]]>chEF[chOrder[k]])
		{
			newGenOrder[i]	=	popOrder[j];
			i++;
			j++;
		}
		else
		{
			copyArray(childs+(chOrder[k])*2*n,population+popOrder[k+elite]*2*n,2*n);
			popEF[popOrder[k+elite]]	=	chEF[chOrder[k]];
			newGenOrder[i]				=	popOrder[k+elite];
			i++;
			k++;
		}
	}
	while(j<elite)
	{
		newGenOrder[i]	=	popOrder[j];
		i++;
		j++;
	}
	while(k<populationSize-elite)
	{
		copyArray(childs+(chOrder[k])*2*n,population+popOrder[k+elite]*2*n,2*n);
		popEF[popOrder[k+elite]]	=	chEF[chOrder[k]];
		newGenOrder[i]				=	popOrder[k+elite];
		i++;
		k++;
	}
}
void ShowEmbToArr(int gridSize,int *MI,int *Emb,int n,int m,int x,int y,int x1,int y1,float *V,float *E)
{
	double	kx	=	(x1-x)*10.0/(10.0*gridSize),
			bx	=	x-kx,
			ky	=	(y1-y)*10.0/(10.0*gridSize),
			by	=	y-ky;

	float	r	=	(kx<ky?kx/3:ky/3);
	
	int i,v1,v2;
	for(i=1;i<=n;i++)
	{
		V[(i-1)*3]	=	Emb[(i-1)*2]*kx+bx;
		V[(i-1)*3+1]=	Emb[(i-1)*2+1]*ky+by;
		V[(i-1)*3+2]=	r;
	}
	for(i=1;i<=m;i++)
	{
		v1	=	MI[(i-1)*2];
		v2	=	MI[(i-1)*2+1];
		E[(i-1)*4]	=	Emb[(v1-1)*2]*kx+bx;		
		E[(i-1)*4+1]=	Emb[(v1-1)*2+1]*ky+by;		
		E[(i-1)*4+2]=	Emb[(v2-1)*2]*kx+bx;		
		E[(i-1)*4+3]=	Emb[(v2-1)*2+1]*ky+by;
	}
}

//-=Algorithm=-
int GDGA(int *Survior,int n,int m,int *MI)
{
	int		i,i1;

	gridSize=calculateGridSize(n);
	srand(time(NULL));
	
	//popSize
	int		populationSize=10;

	int		*population	=	new int[populationSize*n*2];
	double	*popEF		=	new double[populationSize];
	int		*popOrder	=	new int[populationSize];

	int		*childs		=	new int[populationSize*n*2];
	double	*chEF		=	new double[populationSize];
	int		*chOrder	=	new int[populationSize];

	for(i1=0;i1<populationSize;i1++)
	{
		chOrder[i1]	=i1;
		popOrder[i1]=i1;
	}
	
	int		*parents	=	new int[populationSize];

	int		*newGenOrder=	new int[populationSize];

	//exchannging
	int		*swap	=	NULL;
	
	//degrees of vertices
	int		*Deg	=	new int[n];
	calculateDeg(MI,Deg,m,n);
	//optimal edge length
	double	optLen	=0;
	optLen=optLenCalculate(n);
	//Movements
	int		*Movements=	new int[16];
	Movements[0]	=	1;
	Movements[1]	=	0;
	Movements[2]	=	0;
	Movements[3]	=	1;
	Movements[4]	=	1;
	Movements[5]	=	1;
	Movements[6]	=	-1;
	Movements[7]	=	0;
	Movements[8]	=	0;
	Movements[9]	=	-1;
	Movements[10]	=	-1;
	Movements[11]	=	-1;
	Movements[12]	=	1;
	Movements[13]	=	-1;
	Movements[14]	=	-1;
	Movements[15]	=	1;
	
	//possibility of mutate
	int		*PMutate=new int[8];	
	PMutate[0]	=	10;
	PMutate[1]	=	5;
	PMutate[2]	=	5;
	PMutate[3]	=	5;
	PMutate[4]	=	10;
	PMutate[5]	=	5;
	PMutate[6]	=	12;
	PMutate[7]	=	5;
	//convergence
	double	eps	=0.05;
	int		conv;
	
	double	*EF=new double[k];
	for(i=0;i<k;i++)
	{
		EF[i]	=	eps*i;
	}

	gridSize	=	calculateGridSize(n);
	optLen		=	optLenCalculate(n);
	
	int		iterations=0;
	//random generating and norming
	generatePopulation(population,n,populationSize);
	calculateEFforPop(population,popEF,n,MI,m,optLen,populationSize);
	sort2(popOrder,popEF,populationSize);
	i=0;	
	do
	{
		for(i=0;i<k-1;i++)
		{
			EF[i]	=	EF[i+1];
		}
		EF[k-1]	=	popEF[popOrder[0]];	

		chooseParents1(population,parents,n,popOrder,populationSize);
		generateChilds1(parents,childs,n,MI,m,Movements,PMutate,Deg,populationSize,population);
		calculateEFforPop(childs,chEF,n,MI,m,optLen,populationSize);
		sort2(chOrder,chEF,populationSize);		

		generateNextGen2(population,popOrder,childs,chOrder,n,populationSize,popEF,chEF,newGenOrder);
		swap		=	newGenOrder;
		newGenOrder	=	popOrder;
		popOrder	=	swap;
		swap		=	NULL;

		conv=isConvergence(EF,eps,k);
		iterations++;
	}
	while((!conv)&&(iterations<maxIter));
	copyArray(population+(popOrder[0])*n*2,Survior,2*n);

	
	delete[populationSize*n*2]	population;
	delete[populationSize]		chOrder;
	delete[populationSize]		popEF;
	delete[populationSize]		popOrder;
	delete[populationSize*n*2]	childs;
	delete[populationSize]		chEF;
	delete[populationSize]		parents;
	delete[populationSize]		newGenOrder;
	delete						swap;
	delete[n]					Deg;
	delete[16]					Movements;
	delete[8]					PMutate;
	delete[k]					EF;

	return iterations;
}
//-=Alorithm=-
void GDGAToArr(int n,int m,int *MI,float *V,float *E,int x,int y,int x1,int y1)
{
	int			*Surv=new int[n*2];

	GDGA(Surv,n,m,MI);
	ShowEmbToArr(gridSize,MI,Surv,n,m,x,y,x1,y1,V,E);

	delete[n*2] Surv;
}